package com.hqq.exercise.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * BinaryTreePaths 找到从根节点到叶子节点的所有路径
 * 题目描述:
 * 给一棵二叉树，找出从根节点到叶子节点的所有路径
 * 样例输入:
 * 1
 * /   \
 * 2     3
 * \
 * 5
 * 样例输入:
 * [
 * "1->2->5",
 * "1->3"
 * ]
 * 思路:
 * 首先遍历节点，先判断左子树是否为空 不为空的话放入栈并且遍历左子树的左子树
 * 如果为空 遍历右子树
 * Created by heqianqian on 2017/9/8.
 */
public class BinaryTreePaths {

    /**
     * 保存路径
     */
    private List<String> paths = new ArrayList<>();

    /**
     * @param root the root of the binary tree
     * @return all root-to-leaf paths
     */
    public List<String> binaryTreePaths(TreeNode root) {
        // write your code here
        findAllPaths(root, new Stack<>());
        return paths;
    }

    /**
     * @param root the root of the binary tree
     * @param path all root-to-leaf paths
     */
    private void findAllPaths(TreeNode root, Stack<Object> path) {
        if (root == null) {
            return;
        }
        path.push(root.val);
        if (root.left == null && root.right == null) {
            paths.add(handle(path));
        }
        if (root.left != null) {
            findAllPaths(root.left, path);
        }
        if (root.right != null) {
            findAllPaths(root.right, path);
        }
        path.pop();
    }

    /**
     * Find path by recursion
     *
     * @param root the root of the binary tree
     * @return all path in binary tree
     */
    public List<String> findAllPaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) {
            return paths;
        }
        //使用栈保存路径经过的节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.peek();
            if (node.left == null && root.right == null) {
                paths.add(handlePath(stack));
            }
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
            stack.pop();
        }
        return paths;
    }

    /**
     * @param path path
     * @return special format of path
     */
    private String handlePath(Stack<TreeNode> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size() - 1; i++) {
            sb.append(path.get(i).val).append("->");
        }
        sb.append(path.peek());
        return sb.toString();
    }

    /**
     * @param path path
     * @return special format of path
     */
    private String handle(Stack<Object> path) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size() - 1; i++) {
            sb.append(path.get(i)).append("->");
        }
        sb.append(path.peek());
        return sb.toString();
    }
}
